﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace MyShowBinTree
{
    public partial class Form1 : Form
    {
        int radio = 50;
        int lineHeight = 80;
        int colWidth = 80;
        Font font = new Font("Consolas", 18, FontStyle.Bold);
        private TreeNode root = null;
        public Form1()
        {
            InitializeComponent();
        }
        public void CreateTreeNode()
        {
            root = new TreeNode(10);
            root.left = new TreeNode(8);
            root.left.left = new TreeNode(6);
            root.left.left.left = new TreeNode(4);
            root.left.left.right = new TreeNode(7);
            root.right = new TreeNode(15);
            root.right.left = new TreeNode(13);
            root.right.left.left = new TreeNode(15);
            root.right.left.right = new TreeNode(16);
            root.right.right = new TreeNode(18);
            root.right.right.left = new TreeNode(17);
            root.right.right.right = new TreeNode(19);
        }

        private void 开始ToolStripMenuItem_Click(object sender, EventArgs e)
        {
            CreateTreeNode();
            ShowTree();
        }

        public void ShowTree()
        {
            Image img = Common.GetTreeImage(root);
            MyPic.Image = img;
        }

        private List<int> beList = null;
        private List<int> miList = null;
        private List<int> afList = null;
        private void 遍历ToolStripMenuItem_Click(object sender, EventArgs e)
        {
            if (root != null)
            {
                beList = BeforeEach(root);
                miList = MiddleEach(root);
                afList = AfterEach(root);
                string mess = "前序:   " + string.Join<int>(",", beList);
                mess += Environment.NewLine + "中序:   " + string.Join<int>(",", miList);
                mess += Environment.NewLine + "后序:   " + string.Join<int>(",", afList);
                txtData.Text = mess;
            }
        }

        private List<int> BeforeEach(TreeNode node)
        {
            List<int> list = new List<int>();
            list.Add(node.value);
            if (node.left != null)
            {
                List<int> lList = BeforeEach(node.left);
                list.AddRange(lList);
            }

            if (node.right != null)
            {
                List<int> rList = BeforeEach(node.right);
                list.AddRange(rList);
            }

            return list;
        }


        private List<int> MiddleEach(TreeNode node)
        {
            List<int> list = new List<int>();

            if (node.left != null)
            {
                List<int> lList = MiddleEach(node.left);
                list.AddRange(lList);
            }
            list.Add(node.value);
            if (node.right != null)
            {
                List<int> rList = MiddleEach(node.right);
                list.AddRange(rList);
            }

            return list;
        }

        private List<int> AfterEach(TreeNode node)
        {
            List<int> list = new List<int>();

            if (node.left != null)
            {
                List<int> lList = AfterEach(node.left);
                list.AddRange(lList);
            }

            if (node.right != null)
            {
                List<int> rList = AfterEach(node.right);
                list.AddRange(rList);
            }

            list.Add(node.value);
            return list;
        }

        private void 中序和后序ToolStripMenuItem_Click(object sender, EventArgs e)
        {
            if (miList != null && afList != null)
            {
                TreeNode node = BuildTreeMiddleAndAfter(miList, afList);
                root = node;
                ShowTree();
            }
        }

        private int inIndex;
        private int postIndex;
        private TreeNode BuildTreeMiddleAndAfter(List<int> miList, List<int> afList)
        {
            //前序: 10,8,6,4,7,15,13,18,17,19
            //中序: 4,6,7,8,10,13,15,17,18,19
            //后序: 4,7,6,8,13,17,19,18,15,10


            inIndex = miList.Count - 1;
            postIndex = afList.Count - 1;
            return buildTree(miList, afList, null);
        }


        public TreeNode buildTree(List<int> miList, List<int> afList, TreeNode endNode)
        {
            if (postIndex < 0)
            {
                return null;
            }
            //前序: 10,8,6,4,7,15,13,18,17,19
            //中序: 4,6,7,8,10,13,15,17,18,19
            //后序: 4,7,6,8,13,17,19,18,15,10
            TreeNode current = new TreeNode(afList[postIndex]);
            postIndex--;

            if (miList[inIndex] != current.value)
            {
                current.right = buildTree(miList, afList, current);
            }

            inIndex--;
            if (endNode == null || miList[inIndex] != endNode.value)
            {
                current.left = buildTree(miList, afList, endNode);
            }
            return current;
        }
    }
}
